package zuosheng.day1;

/**
 * @author lj
 * @Description: 给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。
 * @date 2020-10-31 15:43
 * @QQ 851477108
 */


public class Code_08_NetherlandsFlag {
    public static void main(String[] args) {
        int [] arr= {1,3,6,2,5};
        int num=4;
        partition(arr, 0, arr.length - 1, num);
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }

    public static int[] partition(int[] arr,int l,int r,int num){
        int less = l - 1;
        int more = r ;
        int index = l;
        while (index<more){
            if (arr[index]<num){
                swap(arr,++less,index++);
            }else if (arr[index]>num){
                swap(arr,--more,index);
            }else {
                index++;
            }
        }
        return new int[] {less + 1,more };
    }

    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
